#include "BTreeNode.h"
#include <iostream>

using namespace std;

/************helper fxn**************/

//initialize any buffer array to junk value
void bufferInit(char* a_buffer)
{
    memset(a_buffer, 0xffffffff, PageFile::PAGE_SIZE);
}

//comparison function for vector sort
bool comparePairs(const IdKeyPair& left, const IdKeyPair& right)
{
    return left.key < right.key;
}

//print out elements of vector pairs
void printVector(const vector<IdKeyPair>& vectA)
{

    printf("\ntest:\n");
    for (int i=0; i<vectA.size(); i ++)
    {
        printf("key: %d, pid: %d \n", vectA[i].key, vectA[i].pid);
    }
}
/************helper fxn end**************/

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */



RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
	return ((rc = pf.read(pid,buffer) < 0) ? rc : 0);
}

/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	RC rc;
	return ((rc = pf.write(pid,buffer) < 0) ? rc : 0);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */

int BTLeafNode::getKeyCount()
{ 
	int size = PageFile::PAGE_SIZE;
	//maxCount is the maximum number of record ids on a leaf node.
	int maxCount = (size - sizeof(int)-1)/(sizeof(RecordId)+sizeof(int)) - 1;
	int count = 0;
	int key = 0;
	for(int i = 0; (i < size - sizeof(int)-1) && count <= maxCount; 
        i+=(sizeof(RecordId)+sizeof(int))){
        
		memcpy(&key, (buffer + i), sizeof(int));
		if(key >= 0)
			count++;
		else
			return count;
	}
	
	return count;
}



void BTLeafNode::initialize(){
	memset(buffer, 0, PageFile::PAGE_SIZE);
	int x = -1;
	memcpy(buffer, &x,sizeof(int));
}

void BTLeafNode::printBuffer() 
{
	int mbuffer[PageFile::PAGE_SIZE/4];
	memcpy(mbuffer,buffer, PageFile::PAGE_SIZE);
	int i = 0;
	while(i<15){
		cout<<(i+1)<<": "<<mbuffer[i]<<endl;
		i++;
	}
	cout<<"Next: "<<mbuffer[PageFile::PAGE_SIZE/4 - 1]<<endl;
	int count = getKeyCount();
	cout<<"pCount: "<< count<<endl;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int count = getKeyCount();
	size_t recordSize = (sizeof(RecordId)+sizeof(int));
	int maxCount = ((PageFile::PAGE_SIZE) - sizeof(int))/(sizeof(RecordId)+sizeof(int))-1;
	if( count >= maxCount)
		return RC_NODE_FULL;
    
	int storedkey;
	int place = 0;
    
	for(int i = sizeof(RecordId); i < count * recordSize; i += recordSize)
	{
        
		memcpy(&storedkey, (buffer + i), sizeof(int));
		if(key <= storedkey)
			break;
		else
			place++;
	}
	if(place == count)	
	{
		memcpy((buffer + count * recordSize),&rid, sizeof(RecordId));
		memcpy((buffer + count * recordSize + sizeof(RecordId)),&key, sizeof(int));
		int x =-1;
		memcpy((buffer + count * recordSize + sizeof(RecordId) + sizeof(int)),&x, sizeof(int));
	}
	else
	{
		char tempBuffer[PageFile::PAGE_SIZE];
		
		//create a temporary copy of the buffer
		memcpy(tempBuffer, buffer, PageFile::PAGE_SIZE);
		//move the bigger keys one slot to the left
		memcpy((buffer + (place +1) *recordSize), (tempBuffer + place*recordSize), (count-place)*recordSize);
		//insert the new key and rid to the correct spot
		memcpy((buffer + place * recordSize),&rid, sizeof(RecordId));
		memcpy((buffer + place * recordSize + sizeof(RecordId)),&key, sizeof(int));
		int x =-1;
		memcpy((buffer + count * recordSize + sizeof(RecordId) + sizeof(int)),&x, sizeof(int));
        
	}
	
	return 0;
	
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */


RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
    
	int keyCount = getKeyCount();
	int maxSize = PageFile::PAGE_SIZE;
	int split = (getKeyCount()) / 2;
	size_t recordSize = (sizeof(RecordId)+sizeof(int));
	int midKey;
	RC rc;
	//PageId pid = getNextNodePtr();
	//get the middle key
	memcpy(&midKey, (buffer + split*recordSize + sizeof(RecordId)), sizeof(int));
	
	memcpy(sibling.buffer, (buffer + split*recordSize), (maxSize - 1 - split*recordSize - sizeof(PageId)));
	PageId pid = sibling.getNextNodePtr();

	int x = -1;
	memcpy((buffer + (split*recordSize)),&x, sizeof(int));
	siblingKey = midKey;
	
	if((rc = sibling.setNextNodePtr(getNextNodePtr())) != 0)
        return rc;
	
	if((rc = setNextNodePtr(pid)) != 0)
        return rc;
    
	
	if (key < midKey){
		if((rc = insert(key,rid)) != 0)
			return rc;
	}
	else{
		if((rc = sibling.insert(key,rid)) != 0)
			return rc;
	}
	
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int finish = getKeyCount() - 1;
	size_t recordSize = (sizeof(RecordId)+sizeof(int));
	int start=0;
	//int middle;
	int key;
	while(start <= finish){
		//middle = (finish - start)/2 + 1;
		memcpy(&key, (buffer + start * recordSize + sizeof(RecordId)), sizeof(int));
		if(key >= searchKey){
			eid = start;
			return 0;
		}
		
		start++;
	}
	eid=-1;
	return RC_NO_SUCH_RECORD;
}	

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	size_t recordSize = (sizeof(RecordId)+sizeof(int));
	int maxCount = ((PageFile::PAGE_SIZE) - sizeof(int))/(sizeof(RecordId)+sizeof(int));
	if(	eid >= maxCount)
		return RC_INVALID_ATTRIBUTE;
    
	memcpy(&rid, (buffer + eid * recordSize), sizeof(RecordId));
	memcpy(&key, (buffer + eid * recordSize + sizeof(RecordId)), sizeof(int));
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid = -1;
	int maxSize = PageFile::PAGE_SIZE;
	memcpy(&pid, buffer + maxSize - 4, sizeof(int));
	return pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 	
	if(pid < 0)
		return RC_INVALID_PID;
	int maxSize = PageFile::PAGE_SIZE;
	memcpy(buffer + maxSize - 4, &pid, sizeof(int));
	return 0; 
}



/*
 * Constructor for non-leaf node
 * initialize private variables with temporary values
 * default first and last pid is -1 because node is empty on construction
 */

BTNonLeafNode::BTNonLeafNode()
    :num_key(0),firstPid(-1),lastPid(-1)
{
    memset(buffer, 0xffffffff, PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
    //fill buffer with null string
    int temp = pf.read(pid, buffer);//contain error code or 0
    //get firstPid
    memcpy(&firstPid, buffer+4, sizeof(PageId));
    if (temp == 0)
    {
        getKeyCount();//set num of keys in private variable
    }
    else
        printf ("\n Read Error\n");
    return temp;
}

    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
    int temp = pf.write(pid, buffer);
    return temp;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node 
 * & save #keys into private var num_key
 * Assume, node is already designated by read fxn
 */
int BTNonLeafNode::getKeyCount()
{ 
    //first four bytes store number of keys in the node;
    int count;
    memcpy(&count, &buffer, 4);
    num_key=count;
    return count;
}

/*
 * update lastPid variable and num_key private variables
 * sets lastPid from last 4 bytes in buffer
 */
void BTNonLeafNode::updatePidKey()
{
    int cur_num_keys=getKeyCount();
    int recordSize=4+sizeof(PageId);
    char* tempArray=buffer+recordSize;
    memcpy(&lastPid, tempArray+cur_num_keys*recordSize+4, sizeof(PageId));
    memcpy(&firstPid, buffer+4, sizeof(PageId));
}

/*
 *  Set number of keys in first 4 bytes
 */
void BTNonLeafNode::setKeyCount(int countKeys)
{
    memcpy(buffer, &countKeys, 4);
    num_key=countKeys;

}


/*
 * Insert a (key, pid) pair to the node.
 * Assume that page already read into main memory
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */

RC BTNonLeafNode::insert(int key, PageId pid)
{ 
    int tempK, j_byte=0;
    //true if there are key already exists, o.w. false
    //bool dupKey = false;
    PageId tempP;
    IdKeyPair pair;
    vector<IdKeyPair> buffPair;
    //skip the count 4 bytes and the first PageId 4 bytes
    char* start = buffer+4+sizeof(PageId);
    
    //check valid pid
    if (pid<0) return RC_INVALID_PID;

    //check boundary size of node
    int recordSize= 4 + sizeof(PageId);
    int cur_size = getKeyCount()*recordSize;
    if (cur_size + recordSize >= PageFile::PAGE_SIZE)
        return RC_NODE_FULL;

    //retrieve pid and key from buffer
    //does not include last pid
    for (int i=0; i < num_key; i++)
    {
        //cpy key byte
        memcpy(&tempK, start+j_byte, 4);
        //copy pid byte
        memcpy(&tempP, start+j_byte+4, sizeof(PageId));

        if(key == tempK) //update instead of inserting
        {
            memcpy(start+j_byte+4, &pid, sizeof(PageId));
            //dupKey=true;//duplicate insert
            return 0;
            //break;
        }
        else
        {//insert into vector to sort
            pair.key=tempK;
            pair.pid=tempP;
            buffPair.push_back(pair);
        }
        j_byte+=4+sizeof(PageId);
    }



    //if there are no duplicates, then insert new key,pid & sort
    int cur_num_keys=num_key;
    pair.pid=pid;
    pair.key=key;
    buffPair.push_back(pair);
    sort(buffPair.begin(), buffPair.end(),comparePairs); 
    cur_num_keys++;
    memcpy(buffer, &cur_num_keys, 4);
    int vectKey;
    PageId vectPid;
    //insert vector pairs into buffer
    for (int j=0; j<buffPair.size(); j++)
    {
        vectKey=buffPair[j].key;
        vectPid=buffPair[j].pid;
        memcpy(buffer+j*recordSize+recordSize,&vectKey,4);
        memcpy(buffer+j*recordSize+recordSize+4,&vectPid,sizeof(PageId));
    }
    updatePidKey();//update num_key and update lastPid
    return 0; 
}

/* Assume node is already full
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
    if(pid < 0) return RC_INVALID_PID;

    int keyCount = getKeyCount();
    int maxSize = PageFile::PAGE_SIZE;
    int split;
    size_t recordSize = (sizeof(PageId) + 4);
    int lastHalf;// = keyCount-split-1;//#keys in last half of node
    char* tempBuff=new char[maxSize+recordSize];
    char* newBuff=new char[maxSize];
    memcpy(tempBuff, buffer, recordSize);//copy first 8 bytes
    //k is the max count of new buffer
    int i=0,k=0,t_key,t_pid;
    bool keyOnce=true;
    while(readEntry(i, t_key, t_pid)==0)
    {
        //compare key & pid then insert 
        if(t_key == key)
        {
            memcpy((tempBuff+k*recordSize+recordSize), &key, 4);
            memcpy((tempBuff+k*recordSize+recordSize+4), &pid, sizeof(PageId));
            i++;
            k++;
        }
        else if(t_key > key && keyOnce)
        {
            memcpy((tempBuff+k*recordSize+recordSize), &key, 4);
            memcpy((tempBuff+k*recordSize+recordSize+4), &pid, sizeof(PageId));
            keyOnce=false;
            k++;
        }
        else
        {
            memcpy((tempBuff+k*recordSize+recordSize), &t_key,4);
            memcpy((tempBuff+k*recordSize+recordSize + 4), &t_pid,sizeof(PageId));
            i++;
            k++;
        }
    }

    keyCount=k; 
    split=(k)/2;
    lastHalf=keyCount-split-1;
    //get mid key of current node
    memcpy(&midKey, tempBuff + recordSize+ split*recordSize, 4);
    //put the last half of the buffer excluding midkey into sibling node
    memcpy(sibling.buffer+4, tempBuff + 4+recordSize + split*recordSize, (lastHalf)*recordSize+4);
    //copy back values to original buffer
    memcpy(buffer, tempBuff, recordSize+split*recordSize);
    //update pid and key count for both nodes
    setKeyCount(split);
    sibling.setKeyCount(lastHalf);
    updatePidKey();
    sibling.updatePidKey();
    return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * Assume that buffer is already sorted.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
    int recordSize= 4+ sizeof(PageId);
    char* start=buffer+recordSize;
    int comp_key; 
    int keyCount=getKeyCount();
	if(keyCount==0) return RC_NO_SUCH_RECORD;//no keys to search
        

    //loop through buffer and find child node pointer of the search key
    //the left ptr= less than
    //right ptr = equal or greater
    for (int i=0; i < keyCount; i++)
    {
        memcpy(&comp_key, start+recordSize*i,4);
        //because buffer is sorted, if searchKey < current key
        //the left pointer would be returned
        if(searchKey < comp_key) 
        {
            memcpy(&pid, start+recordSize*i-4, sizeof(PageId));//backtrack from key to get pointer
            break;
        }
        //found matching key or
        //reached the last key without finding ptr
        //so output the right pid
        else if(searchKey==comp_key || i==keyCount-1)
        {
            memcpy(&pid, start+recordSize*i+4, sizeof(PageId));
            break;
        }
        else{}        

    }

    return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
    char* temp = buffer;
    int i=1;
    if(pid1 < 0 || pid2 < 0) return RC_INVALID_PID;
    memcpy(temp, &i, 4);//copy key count;
    temp=temp+4;
    memcpy(temp, &pid1, sizeof(PageId));
    temp=temp+sizeof(PageId);
    memcpy(temp, &key, 4);
    temp=temp+4;
    memcpy(temp, &pid2, sizeof(PageId));

    return 0;
}

//Used to debug the buffer:
//print buffer to console in a readable format
void BTNonLeafNode::printBuffer() const
{
    int key_count,tempP,tempK;

    int recordSize=4 + sizeof(PageId);
    memcpy(&key_count, buffer, 4);
    memcpy(&tempP, buffer+4, sizeof(PageId));
    printf("\n first pid: %d", tempP);

    for (int i=0; i<key_count; i++)
    {
        //get key
        memcpy(&tempK, buffer+i*recordSize+recordSize, 4);
        //get pid
        memcpy(&tempP, buffer+i*recordSize+4+recordSize,sizeof(PageId));
        printf("\n key: %d,pid: %d", tempK,tempP);
    }
}

//read key,pid pair at pos eid
RC BTNonLeafNode::readEntry(int eid, int& key, PageId& pid)
{
    size_t recordSize = (sizeof(PageId) + 4);
    int maxCount = getKeyCount();
    if(eid >= maxCount) return RC_INVALID_ATTRIBUTE;

    memcpy(&key, (buffer+eid*recordSize+recordSize), sizeof(int));
    memcpy(&pid, (buffer+eid*recordSize+recordSize+4), sizeof(PageId));
    return 0;
}



